package a1_p04_jw_kw.searchalgo;

import java.util.ArrayList;
import java.util.List;
import java.util.Set;
import java.util.Stack;

import org.jgrapht.Graph;
import org.jgrapht.graph.DefaultWeightedEdge;

import a1_p04_jw_kw.struct.Node;

public class DepthFirstSearch {
	Stack<Node> stack = new Stack<Node>();
	Graph<Node, DefaultWeightedEdge> g;
	List<Node> visited = new ArrayList<Node>();
	
	ArrayList<Node> bestWay = new ArrayList<Node>();
	
	Node target;
	
	int count = 0;
	
	public DepthFirstSearch(Graph<Node, DefaultWeightedEdge> g) {
		this.g = g;
		
	}
	
	public void startSearch(String source, String target) {
		this.target = getNode(target);
		if (dfs(getNode(source)) != null) {
			System.out.println("knoten gefunden");
			
		} else { 
			System.out.println("knoten nicht gefunden");
		}
		
		System.out.println("Bestway: " + this.bestWay);
		System.out.println("Besuchte Knoten: " + count);
		
	} 
	
	private Node dfs(Node source) {
		//mark source as visited
		visited.add(source);
		count++;
		
		System.out.println("visiting node: " + source.name);

		//if source is the target return itself
		if (source.equals(this.target)) {
			this.bestWay.add(source);
			
			return source; 
		} else {
			//push all successors to the stack
			for (Node node : getSuccessor(source)) {
				if ((visited.contains(node)) || stack.contains(node)) {
					System.out.println("node " + node.name + " already visited or registered");
					
				} else {
					System.out.println("push node to stack: " + node.name);
					stack.push(node);
				
				}
			}
			
			//while the stack isnt empty get next vertex to visit and run dfs()
			while (!stack.isEmpty()) {
				Node nextNode = stack.pop();
				
				//call dfs() recursively
				Node retNode = dfs(nextNode);
				if (retNode != null) {
					this.bestWay.add(source);
					return retNode;
					
				} else {
					return null;
					
				}
			}
		}
		
		return null;
	}
	
	private ArrayList<Node> getSuccessor(Node node) {
		ArrayList<Node> successor = new ArrayList<Node>();
		Set<DefaultWeightedEdge> edgeSet = g.edgeSet();
		
		for (DefaultWeightedEdge edge : edgeSet) {
			if (g.getEdgeSource(edge).equals(node)) {
				Node target = g.getEdgeTarget(edge);
				
				if (!visited.contains(target)) {
					successor.add(target);
					
				}
			}
		}
		
		return successor;
	}
	
	private Node getNode(String name) {
		for (Node node : g.vertexSet()) {
			if (node.name.equals(name)) {
				return node;
				
			}
		}
		
		return null;
	}
}
